package DP.Lesson7;


/**
 * https://leetcode-cn.com/problems/edit-distance/
 */
public class EditDistance {

    /*
    这题的关键思路是从最后往前思考
    假设字符串s1, s2 差最后一个字符的操作，那他的最小编辑距离就是
    dp[i][j] = min{dp[i][j], dp[j-1]+1}
    然后，比对最后一个字符串，如果相等就什么都不用做
    dp[i][j]的含义是s1[0....i] 与 s2[0....j]之间编辑举例
    初始条件，当
     */
    public int minDistance(String word1, String word2) {
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();
        int i,j,m=s1.length,n=s2.length;
        int[][] dp=new int[m+1][n+1];
        dp[0][0] = 0;
        for(i=1; i<=m; i++) dp[i][0] = i;//表示，s1是空串，s2变成s1需要的编辑距离
        for(i=1; i<=n; i++) dp[0][i] = i;//表示，s2是空串，s2变成s1需要的编辑距离

        //记得要从1开始，不能从2，从2开始就直接跳过第一个字符了
        for(i=1; i<=m; i++){
            for(j=1; j<=n;j++){
                if( s1[i-1] == s2[j-1]){//如果相等，就不需要修改，取i-1 j-1的dp值就可以了
                    dp[i][j] = dp[i-1][j-1];
                }else{//如果不相等，有几种操作办法，替换、删除、增加，取最小
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
            }
        }

        return dp[m][n];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public int NMinDistance(String[] words, String word2) {

        return 0;
    }


    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
